perm filename A20[106,RWF] blob
sn#774621 filedate 1984-10-31 generic text, type C, neo UTF8
COMMENT ā VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Algorithms
C00015 ENDMK
Cā;
Algorithms
by
Robert W. Floyd
Copyright l983
An algorithm is the idea of a particular method of computation, like the
idea of addition and subtraction using carries and borrows most of us
learned in school. As with other ideas, an algorithm expressed in one
language can be translated into another; the choice of language is not an
essential part of the algorithm. Familiar algorithms include those for
addition, subtraction, multiplication, and division; those for solving
simultaneous equations by successive elimination of variables; that for
differentiating a formula with respect to a variable; those for estimating
the area under a curve by approximation with line segments, etc. One of
the oldest, due to Euclid, finds the greatest common divisor of two
positive numbers:
(1) Let x be the larger number, y the smaller.
(2) If y=0, x is the answer.
(3) Otherwise, let the new value of y be the remainder when x is divided
by y; let the new value of x be the old value of y. Return to Step
(2).
Example: the greatest common divisor of 195 and 75. Successive values of
x and y are:
x = 195, y = 75
x = 75, y = 45
x = 45, y = 30
x = 30, y = 15
x = 15, y = 0
The answer is 15
An algorithm can be expressed in a language intelligible to man, machine,
or both. Euclid's algorithm, expressed in a language more suitable to be
carried out by a machine, looks like:
GET X
GET Y
IF X < Y THEN SWAP X WITH Y
LABEL A
IF Y=0 THEN RETURN RESULT = X
SET R = REMAINDER OF X DIVIDED BY Y
SET X = Y
SET Y = R
GO TO STEP A.
Computers are machines to carry out algorithms; to be useful, they must be
able to execute long, complicated algorithms on numerous data quickly and
reliably. A computer carries out an algorithm as expressed in one of
several precisely defined languages for that computer. An algorithm
expressed in a language executable by some actual computer is called a
program.
Programming, the design of programs, consists of two parts, often
interwoven: the design of an algorithm to solve a problem, and the
expression of that algorithm as a program within the limited notations of
a particular computer language. To learn to program, you must learn and
use some particular programming language, just as music is learned on some
particular instrument. The core of learning to program, though, is
learning to design algorithms.
In CS106, we use the Pascal programming language. It is popular with users
of small to medium-sized computers (``micros'' and ``minis''), and has
become a common language for communication of algorithms in print.
Pascal is not as well suited for the expression of business problems as
PL-I and COBOL; nor as well suited for engineering calculations as
FORTRAN; nor as well suited for processing symbolic information as SNOBOL
and LISP; nor ... well, you get the idea. No matter. Most of what you
will want to program can be said very similarly in most programming
languages, and after you learn one such language, you can learn any other
in a day or so.
So, you will learn Pascal, and, with labor and attention, how to design an
algorithm systematically and correctly. You won't learn all of Pascal from
the course. This is no oversight; parts of Pascal are largely of use to
more experienced programmers, and parts are of marginal usefulness. If
you have trouble with the problems, it won't be because you don't know
Pascal well enough.
My goals are to teach you to systematically and correctly design computer
programs more complicated than anything else you have ever designed in
your life, programs so sensitive to error that a single mis-typed symbol
will probably make the program incorrect. Ideally, you will learn to
program in such a way that your first drafts of programs will contain few
errors other than slips of the pen, and that your programs can be
systematically tested and corrected (``debugged'').
Programming without standards of quality is easy. Programming is a
difficult discipline if one believes a program must be utterly trustworthy
on all valid data; that it must detect and report all invalid data; that
its results must be intelligible and unambiguous; that other programmers
must be able to adapt the program to other languages, computers, and
problems than those for which it was originally designed, long after the
original programmer has vanished.
The course notes are interlaced with Rules of Good Programming Practice.
These are only a small subset of the 927 (or was it 928?) eternal truths,
but they are very useful, and we expect you either to adhere to them or
(since they have exceptions) explain why.
We also expect you to take responsibility for yourself. The computer
center can be a difficult environment. The computer may fail for a day at
a time. Lines to use the computer may be hours long at the end of the
quarter. Assignments may be more difficult than intended. We expect you
to begin projects as early as possible; if the computer fails six hours
before a program is due, that is your problem. We expect you to use the
often overloaded computer system in a way considerate to your fellow
students; in particular, when you no longer are sure what you are doing,
get off the computer and let someone else use it. Also, delete any files
you no longer need to release storage capacity for other users. We expect
your programs to work for all valid data, and not just for the test cases
you run; to deliberately design a program that only works for the data on
which it is tested will be considered cheating. We expect you to plan to
spend twelve hours a week on this course (the university guideline for a
4-unit course) including class and computer time; you will find the course
insuitable as part of an 18-unit program.
We expect you, as the assignments become more difficult, to include
adequate explanations of how your program works. Let the hard-pressed
grader, who perhaps just took the course the previous quarter, know in
outline what your methods are. And if your native language is English, we
would appreciate a demonstration of the fact. We expect you to respect the
privacy of other people's computer files; the fact that someone has not
fully protected his files does not give you the right to read them.
Okay, we've told you the worst. On the good side, the teaching assistants,
consultants, and professor are there to help out. Not by doing your work
for you, but by serving as models of how to think about programming. Most
of the time, the computer center is a friendly environment. And the
computer itself is the most versatile tool you will ever use. You have
signed up to vastly extend your powers to use and create information. I
think you will be glad you did.
ALGRMS[1, rfn]